"""
题目：实现图的广度优先搜索，从指定顶点开始遍历所有可达顶点。
"""
class Graph:
    def __init__(self, is_directed=False):
        self.vertices = {}
        self.is_directed = is_directed

    def add_vertex(self, vertex):
        if vertex not in self.vertices:
            self.vertices[vertex] = []

    def add_edge(self, v1, v2):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.vertices[v1].append(v2)
        if not self.is_directed:
            self.vertices[v2].append(v1)

    def bfs_all(graph):
        """
        遍历图中所有连通分量的BFS
        :param graph: 图对象（Graph类实例）
        :return: 按BFS顺序排列的所有顶点列表
        """
        visited = set()  # 记录已访问的顶点（避免重复访问）
        result = []  # 存储最终的遍历结果
        def bfs(start_vertex):
            """处理单个连通分量的BFS（用列表模拟队列，不依赖deque）"""
            queue = [start_vertex]
            visited.add(start_vertex)  # 标记起始顶点为已访问 注意观察：搜集数据时，queue和visited这两个总是同时出现
            # 队列不为空时，循环处理；队列不为空，说明还没遍历完
            while queue:
                current_vertex = queue.pop(0)
                result.append(current_vertex)
                for neighbor in graph.vertices[current_vertex]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
        # 遍历图中所有顶点，确保每个连通分量都被访问
        for vertex in graph.vertices:
            if vertex not in visited:
                # 对未访问的顶点启动BFS（每个未访问顶点对应一个新的连通分量）
                bfs(vertex)
        return result

graph = Graph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 5)
graph.add_edge(6, 7)
graph.add_edge(6, 8)

print("BFS遍历结果:", graph.bfs_all())  # 输出:[0, 1, 2, 3, 4, 5, 6, 7, 8]




